нахождение решения

динамическое программирование
—
[Е.С.Алексеев, А.А.Мячев. Англо-русский толковый словарь по системотехнике ЭВМ. Москва 1993]

динамическое программирование
Раздел математического программирования, совокупность приемов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений. Процессы принятия решений, которые строятся по такому принципу, называются многошаговыми процессами. Математически оптимизационная задача строится в Д. п. с помощью таких соотношений, которые последовательно связаны между собой: например, полученный результат для одного года вводится в уравнение для следующего (или, наоборот, для предыдущего), и т.д. Таким образом, можно получить на вычислительной машине результаты решения задачи для любого избранного момента времени и «следовать» дальше. Д.п. применяется не обязательно для задач, связанных с течением времени. Многошаговым может быть и процесс решения вполне «статической» задачи. Таковы, например, некоторые задачи распределения ресурсов. Общим для задач Д.п. является то, что переменные в модели рассматриваются не вместе, а последовательно, одна за другой. Иными словами, строится такая вычислительная схема, когда вместо одной задачи со многими переменными строится много задач с малым числом (обычно даже одной) переменных в каждой. Это значительно сокращает объем вычислений. Однако такое преимущество достигается лишь при двух условиях: когда критерий оптимальности аддитивен, т.е. общее оптимальное решение является суммой оптимальных решений каждого шага, и когда будущие результаты не зависят от предыстории того состояния системы, при котором принимается решение. Все это вытекает из принципа оптимальности Беллмана (см. Беллмана принцип оптимальности), лежащего в основе теории Д.п. Из него же вытекает основной прием — нахождение правил доминирования, на основе которых на каждом шаге производится сравнение вариантов будущего развития и заблаговременное отсеивание заведомо бесперспективных вариантов. Когда эти правила обращаются в формулы, однозначно определяющие элементы последовательности один за другим, их называют разрешающими правилами. Процесс решения при этом складывается из двух этапов. На первом он ведется «с конца»: для каждого из различных предположений о том, чем кончился предпоследний шаг, находится условное оптимальное управление на последнем шаге, т.е. управление, которое надо применить, если предпоследний шаг закончился определенным образом. Такая процедура проводится до самого начала, а затем — второй раз — выполняется от начала к концу, в результате чего находятся уже не условные, а действительно оптимальные шаговые управления на всех шагах операции (см. пример в статье Дерево решений). Несмотря на выигрыш в сокращении вычислений при использовании подобных методов по сравнению с простым перебором возможных вариантов, их объем остается очень большим. Поэтому размерность практических задач Д.п. всегда незначительна, что ограничивает его применение. Можно выделить два наиболее общих класса задач, к которым в принципе мог бы быть применим этот метод, если бы не «проклятие размерности». (На самом деле на таких задачах, взятых в крайне упрощенном виде, пока удается лишь демонстрировать общие основы метода и анализировать экономико-математические модели). Первый — задачи планирования деятельности экономического объекта (предприятия, отрасли и т.п.) с учетом изменения потребности в производимой продукции во времени. Второй класс задач — оптимальное распределение ресурсов между различными направлениями во времени. Сюда можно отнести, в частности, такую интересную задачу: как распределить урожай зерна каждого года на питание и на семена, чтобы в сумме за ряд лет получить наибольшее количество хлеба?
[ http://slovar-lopatnikov.ru/]

Тематики

• информационные технологии в целом
• экономика

EN

• dynamic programming
• DP

выпуклое программирование
Раздел нелинейного программирования, совокупность методов решения нелинейных экстремальных задач с выпуклыми целевыми функциями (они минимизируются) и выпуклыми системами ограничений. (См. Выпуклость, Вогнутость). Общая задача В.п. состоит в отыскании такого вектора x (т.е. такой точки выпуклого допустимого множества), который доставляет минимум выпуклой функции f(x) или максимум вогнутой функции y(x) (рис. В.4). Для второго случая (выпуклая область допустимых значений и максимум вогнутой функции) ряд авторов предпочитают термин «вогнутое программирование». Выпуклость (вогнутость) важна тем, что гарантирует нахождение оптимального решения задачи, так как соответственно локальные и глобальный экстремумы здесь обязательно совпадают. Критериями оптимальности в первом случае могут быть, например, издержки при различных сочетаниях факторов производства, во втором случае — величина прибыли при этих сочетаниях. Как видим, есть большое сходство между задачами выпуклого (вогнутого) и линейного программирования (последнее можно рассматривать как частный случай первого). Но нелинейность зависимостей делает задачу намного сложнее. Рис.В.4 Задачи вогнутого и выпуклого программирования
[ http://slovar-lopatnikov.ru/]

Тематики

• экономика

EN

• convex programming

дополняющая нежесткость
Термин математического программирования. (См. Жесткость и нежесткость ограничений ЛП). Выполнение так называемых условий Д.н. определяет нахождение совместного оптимального решения сопряженных прямой и двойственной задач. Эти условия используются при анализе чувствительности оптимального решения к изменениям в исходных данных задачи и представляют собой один из способов формулирования Куна — Таккера условий.
[ http://slovar-lopatnikov.ru/]

Тематики

• экономика

EN

• complementary slackness

математическое ожидание
—
[ http://www.iks-media.ru/glossary/index.html?glossid=2400324]

математическое ожидание
Одна из численных характеристик случайной величины, часто называемая ее теоретической средней. Для дискретной случайной величины X математическое ожидание равно сумме произведений возможных значений этой величины на их вероятности: Мх= ?хР(х), а для непрерывной случайной величины — интегралу Обозначается обычно: Mx или Ex (в нашем словаре принято первое из этих обозначений). См. также Среднее значение. Математическое программирование [mathematical programming] - (см. также Оптимальное программирование) — раздел математики, который «… изучает методы решения задач на нахождение экстремума функций (показателя качества решения) при ограничениях в форме уравнений и неравенств»[1]. Оно объединяет различные математические методы и дисциплины исследования операций: линейное программирование, нелинейное программирование, динамическое программирование, выпуклое программирование, геометрическое программирование, целочисленное программирование и др. Общая задача М.п. состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений (см. Область допустимых решений). В самом общем виде задача записывается так: U = f(x) ? max; x ? M, где x = (x1, x2,…, xn); M — область допустимых значений переменных x1,…, xn; f(x) — целевая функция. Частный случай задачи М.п. — «классическая задача». В ней область M представлена равенствами: g(x) = b, где g(x) — вектор функций ограничений, b — вектор констант ограничений. Названные выше разнообразные дисциплины отличаются друг от друга видом целевой функции f(x) и области М. Например, если f(x) и M — линейны, имеем задачу линейного программирования; если же дополнительно ставится условие, чтобы переменные были целочисленны, имеем задачу целочисленного программирования; если зависимость U от x (т.е. форма f) носит нелинейный характер — задачу нелинейного программирования. Развивающаяся область — стохастическое программирование, задачи которого в отличие от детерминированных характеризуются тем, что их исходные данные (все или часть) — суть случайные величины. [1] Математический аппарат экономического моделирования. М.: “Наука”, 1983, стр 8.
[ http://slovar-lopatnikov.ru/]

Тематики

• экономика
• электросвязь, основные понятия

EN

• expectation
• expected value

давать задание — assign

давать непосильное задание — overtask

основна́я / гла́вная зада́ча — the main / chief task

очередна́я зада́ча — immediate task / goal

це́ли и зада́чи — objectives and goals

нелёгкая зада́ча — not an easy job to do

зада́ча на сложе́ние [вычита́ние, деле́ние, умноже́ние] — addition [subtraction, division, multiplication] sum

нау́чная зада́ча — scientific problem